0191. 位1的个数【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 逐位检查
• 3. 🎯 s.2 - Brian Kernighan 算法（更高效）
• 4. 🔗 引用

1. 📝 题目描述

• leetcode

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

---

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

---

提示：

• 1 <= n <= 2^31 - 1

进阶：

• 如果多次调用这个函数，你将如何优化你的算法？

2. 🎯 s.1 - 逐位检查

js

/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function (n) {
  let count = 0
  let mask = 1

  for (let i = 0; i < 32; i++) {
    // 检查当前位是否为 1
    if ((n & mask) !== 0) {
      count++
    }
    // 将 mask 左移一位，检查下一位
    mask <<= 1
  }

  return count
}

• 时间复杂度：$O(1)$，固定循环 32 次
• 空间复杂度：$O(1)$
• 核心思路：
  • 使用一个 mask 从最低位开始检查每一位
  • 通过 n & mask 判断当前位是否为 1
  • 每次循环将 mask 左移一位，检查下一位

3. 🎯 s.2 - Brian Kernighan 算法（更高效）

js

/**
 * @param {number} n
 * @return {number}
 */
var hammingWeight = function (n) {
  let count = 0

  // 处理 JS 中的负数情况
  n = n >>> 0

  // Brian Kernighan 算法
  while (n !== 0) {
    count++
    // 清除最右边的 1
    n &= n - 1
  }

  return count
}

• 时间复杂度：$O(k)$，其中 k 是 1 的个数，最坏情况 $O(k)$
• 空间复杂度：$O(1)$
• 核心思路：
  • 利用 n & (n-1) 的特性：这个操作会清除 n 中最右边的 1
  • 每次操作都会减少一个 1，直到 n 变为 0
  • 操作的次数就是 1 的个数
    • n = 1101, n-1 = 1100, n&(n-1) = 1100, count=1
    • n = 1100, n-1 = 1011, n&(n-1) = 1000, count=2
    • n = 1000, n-1 = 0111, n&(n-1) = 0000, count=3
    • n = 0000，结束循环

4. 🔗 引用

• 汉明重置
  • 百度百科